package com.example.shirotest.study;

import java.text.SimpleDateFormat;
import java.util.Date;

public class SortTest {

    public static void main(String[] args) {
        int[] num = {-8,1,5,4,9,5,3,6,2,8,7}; //无序数组
        //int[] num = {-8,1,2,3,4,5,5,6,7,8,9};  //有序数组

        //冒泡排序法
        //int[] ints = bublleSort(num);

        //选择排序法
        //int[] ints = chooseSort(num);

        //插入排序
        //printArray(insertSort(num));

        //希尔排序（交换法）
        //printArray(shellSort(num));

        //希尔排序（移位法）
        //printArray(shellSort2(num));

        //快速排序法
        //printArray(quickSort(num,0,num.length-1));

        //spendTimeTest();

        System.out.println(15 / 2);
    }

    //打印数组
    private static void printArray(int[] ary){
        for (int anInt : ary) {
            System.out.printf("%d ",anInt);
        }
    }

    //比较不同排序方式的速度
    private static void spendTimeTest(){
        int arrSize = 80000;
        int[] arr = new  int[arrSize];
        for (int i = 0; i < arrSize; i++) {
            arr[i] = (int) (Math.random() * 8000000); //生成一个[0,8000000]的数
        }

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr = simpleDateFormat.format(date);
        System.out.println("Before time : " + dateStr);

        //bublleSort(arr);  //冒泡排序
        //chooseSort1(arr); //选择排序
        //insertSort(arr);  //插入排序
        //shellSort(arr); //希尔排序-交换法
        //shellSort2(arr); //希尔排序-移位法
        //quickSort(arr,0,arr.length-1); //快速排序法 （会出现栈溢出）
        quickSort2(arr,0,arr.length-1);  //正确的快速排序法

        Date date2 = new Date();
        String dateStr2 = simpleDateFormat.format(date2);
        System.out.println("After  time : " + dateStr2);
    }

    public static int[] quickSort2(int[] a, int low, int high) {
        int start = low;
        int end = high;
        int key = a[low];

        while (end > start) {
            // 从后往前比较
            while (end > start && a[end] >= key)
                // 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置
                //然后又从前往后比较
                end--;
            if (a[end] <= key) {
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            // 从前往后比较
            while (end > start && a[start] <= key)
                // 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if (a[start] >= key) {
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            // 此时第一次循环比较结束，关键值的位置已经确定了。
            // 左边的值都比关键值小，右边的值都比关键值大
            // 但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }
        // 递归
        if (start > low)
            quickSort2(a, low, start - 1);// 左边序列。第一个索引位置到关键值索引-1
        if (end < high)
            quickSort2(a, end + 1, high);// 右边序列。从关键值索引+1到最后一个

        return a;
    }

    private static int[] quickSort(int[] arr,int left,int right){
        int l = left; //左下标
        int r = right; //右下标

        //pivot 中轴值
        int pivot = arr[(left + right)/2];
        int temp = 0;
        //while循环的目的是让比pivot小的值放到左边，比pivot大的值放到右边
        while (l < r){
            //在pivot的左边一直找，找到大于等于pivot的值才退出
            while (arr[l] < pivot){
                l += 1;
            }
            //在pivot的右边一直找，找到小于等于pivot的值才退出
            while (arr[r] > pivot){
                r -= 1;
            }
            //如果 l >= r 说明pivot的左右两边的值，已经按照左边全部是小于等于pivot，右边全部的大于等于pivot的值
            if(l >= r){
                break;
            }

            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个arr[l]==pivot,则 r--,右侧下标前移一位（相当自己的数前移一位）
            if(arr[l] == pivot){
                r -= 1;
            }
            //如果交换完后，发现这个arr[r]==pivot,则 l++,左侧下标前移一位（相当自己的数后移一位）
            if(arr[r] == pivot){
                l += 1;
            }

            //如果 l==r ,必须l++ , r-- ,否则会出现栈溢出
            if(l==r){
                l += 1;
                r -= 1;
            }

            //向左递归
            if(left < r){
                quickSort(arr,left,r);
            }
            //向右递归
            if(right > l){
                quickSort(arr,l,right);
            }
        }

        return arr;
    }


    /**
     * 希尔排序   交换法（速度慢）
     * @param ary
     * @return
     */
    private static int[] shellSort(int[] ary){
        int temp = 0;
        for (int gap = ary.length/2;gap > 0;gap /=2){
            for (int i = gap; i < ary.length; i++) {
                //遍历各组中所有元素（共gap组），步长gap
                for (int j = i-gap; j >=0 ; j-=gap) {
                    //如果当前元素大于加上步长的那个元素，说明需要交换
                    if(ary[j] > ary[j+gap]){
                        temp = ary[j];
                        ary[j] = ary[j+gap];
                        ary[j+gap] = temp;
                    }
                }
            }
        }

        return ary;
    }

    /**
     * 希尔排序  移位法（速度快）
     * @param arr
     * @return
     */
    private static int[] shellSort2(int[] arr){
        //增量gap,并逐步的缩小增量
        for (int gap = arr.length/2; gap > 0; gap /=2) {
            //从第gap个元素，逐个对其所有的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-gap]){
                    while (j-gap >=0 && temp < arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }

        return arr;
    }


    /**
     * 插入排序
     * @param ary
     * @return
     */
    private static int[] insertSort(int[] ary){

        for (int i = 1; i < ary.length; i++) {
            int insertValue = ary[i];  //当前数的值
            int preIndex = i-1;   //有序队列中最后的索引

            //退出循序，表示插入的位置已经找到了
            while (preIndex >= 0 && ary[preIndex] > insertValue){
                ary[preIndex+1] = ary[preIndex];
                //ary[preIndex] = insertValue;  //可以放到循环外，就不要放在循环内，可以提高效率
                preIndex--;
            }

            if(preIndex + 1 != i) {
                ary[preIndex + 1] = insertValue;
            }
        }

        return  ary;
    }


    /**
     * 选择排序 (不正确的思路)
     * @param ary
     */
    private static int[] chooseSort2(int[] ary){
        int tmp = 0;

        for (int i = 0; i < ary.length - 1; i++) {
            for (int j = i+1; j < ary.length ; j++) {
                if(ary[i] > ary[j]){
                    //更冒泡操作一样，只是从前面开始固定结果。两两比较和交换会额外增加代码复杂度
                    tmp = ary[i];
                    ary[i] = ary[j];
                    ary[j] = tmp;
                }
            }
        }

        return ary;
    }

    /**
     * 选择排序
     * @param ary
     * @return
     */
    private static int[] chooseSort1(int[] ary){

        for (int i = 0; i < ary.length - 1; i++) {
            int minIndex = i;
            int min = ary[i];
            for (int j = i+1; j < ary.length ; j++) {
                if(min > ary[j]){
                    min = ary[j];
                    minIndex = j;
                }
            }

            if(minIndex != i){
                ary[minIndex] = ary[i];
                ary[i] = min;
            }
        }

        return ary;
    }


    /**
     * 冒泡排序
     * int[] num = {-8,1,5,4,9,5,3,6,2,8,7}; //无序数组
     * int[] num = {-8,1,2,3,4,5,5,6,7,8,9};  //有序数组
     * @param ary
     */
    private static int[] bublleSort(int[] ary){
        int tmp = 0;
        //优化算法，如果一次都没有交换，则说明数字队列是有序的，无效再进行操作
        boolean flag = false;
        for (int i = 0; i < ary.length - 1; i++) {
            for (int j = 0; j < ary.length - 1 -i; j++) {
                if(ary[j] > ary[j+1]){
                    flag = true;
                    tmp = ary[j];
                    ary[j] = ary[j+1];
                    ary[j+1] = tmp;
                }
            }

            if(!flag){
                break;
            }else{
                flag = false;
            }

        }

        return ary;
    }

}
